#include <bits/stdc++.h>
using namespace std;

// 【题目】力扣3. 无重复字符的最长子串
// 【难度】中等
// 【提交】https://leetcode.cn/problems/longest-substring-without-repeating-characters/submissions/675840063/
// 【标签】滑动窗口；哈希表；双指针
class Solution_LC0003 {
public:
    int lengthOfLongestSubstring(string s) {
        // 使用数组记录字符出现次数，ASCII字符集共256个
        int arr[256] = {0};
        int r = 0, l = 0, maxs = 0;  // r:右指针, l:左指针, maxs:最大长度
        
        for (int i = 0; i < s.size(); i++) {
            arr[s[i]]++;    // 当前字符计数加1
            r++;            // 右指针右移
            
            // 如果当前字符出现次数大于1，说明有重复
            while (arr[s[i]] > 1) {
                arr[s[l]]--;    // 左指针字符计数减1
                l++;            // 左指针右移
            }
            
            // 更新最大长度
            maxs = max(maxs, r - l);
        }
        return maxs;
    }
};

/**
 * @brief 学习总结：
 * 本题是经典的滑动窗口问题，使用双指针维护一个不含重复字符的窗口。
 * 
 * 解题思路：
 * 1. 使用左右指针l和r维护当前窗口
 * 2. 使用数组记录窗口中每个字符的出现次数
 * 3. 当右指针遇到重复字符时，移动左指针直到窗口内无重复
 * 4. 在每次循环中更新最大窗口长度
 * 
 * 算法分析：
 * - 时间复杂度：O(n)，每个字符最多被左右指针各访问一次
 * - 空间复杂度：O(1)，使用固定大小的数组
 * 
 * 优点：
 * - 滑动窗口思路清晰，代码简洁
 * - 使用数组代替哈希表，访问效率更高
 * - 双指针移动逻辑正确，能保证找到最优解
 * 
 * 改进建议：
 * 1. 变量命名可以更具描述性：
 *    - 将l改为left，r改为right
 *    - 将maxs改为maxLength
 * 
 * 2. 添加空字符串处理：
 *    if (s.empty()) return 0;
 * 
 * 3. 使用unordered_map支持更大字符集：
 *    unordered_map<char, int> charCount;
 * 
 * 4. 优化代码可读性版本：
 * 
 * int lengthOfLongestSubstring(string s) {
 *     vector<int> charIndex(256, -1);
 *     int maxLength = 0, start = -1;
 *     
 *     for (int i = 0; i < s.length(); i++) {
 *         if (charIndex[s[i]] > start) {
 *             start = charIndex[s[i]];
 *         }
 *         charIndex[s[i]] = i;
 *         maxLength = max(maxLength, i - start);
 *     }
 *     return maxLength;
 * }
 * 
 * 核心思想：
 * 滑动窗口是处理子串/子数组问题的强大工具，通过动态调整窗口边界来满足特定条件，
 * 同时保持线性时间复杂度。
 * 
 * 应用场景：
 * - 无重复字符的最长子串
 * - 最小覆盖子串
 * - 找到字符串中所有字母异位词
 * - 最大连续1的个数等
 */